Routing is executed on various kinds of networks, including the telephone networks, electronic networks and transportation (transport) networks. The main rationale while performing routing involves selecting paths in the network along which information has to be transported based on parameters such as timing delay, unrouted routes, number of hops (intermediate points) and transmission cost.
Routing in large integrated circuits or electronic networks is automatically performed by a routing mechanism known as a “router” that is typically implemented as a software tool on a computer-aided design system (CAD).
In CAD, modern routers try to find routing paths through the routing resource graph. These routers primarily consider the cost of various routing alternatives available in the resource graph as a step prior to routing. Each routing alternative available in the resource graph comprises nets which further comprise a combination of sources and sinks.
Further, static cost and dynamic cost are the main attributes in determining cost of the nets. The static cost for a given net comprises those attributes which do not change across routing iterations. They are further divided into three parameters:
a) a net's span, is the span of the bounding box (a rectilinear region) of the net in x and y directions. A wider span indicates that the pins (sinks) of the net are apart and gives good approximation of total wirelength required to route this net. The wider the span, the higher the chance of a net being un-routable.
FIG. 1 illustrates a net bounding box, X units wide and Y units apart. The half perimeter of the bounding box is approximated byHPWL=X+Y 
b) a net's fan-out, is the number of sinks that the source of the net drives. A higher value of fanout of a net uses longer segments to route the net.Net fan-out=Number of sinks
c) delay sensitivity is the change in the Manhattan distance. It is approximated by considering the change for a given ΔX and ΔY Manhattan distance in a given bounding box. For all possible (ΔX,ΔY) pairs, a delay look up table is computed which stores the best routing delay possible for the corresponding Manhattan pair.Delay sensitivity (neti)=Delay value from timing look up table corresponding to (ΔX, ΔY) pair as computed from the net's bounding box.
The dynamic cost of the nets comprises attributes which change across routing iterations such as number of unroutable sinks, timing deviation and wire length deviation. The attributes are defined in the following description.
i) unroutable sinks are the number of sinks of a net for which a feasible routing tree cannot be constructed.
ii) timing deviation, is the deviation from the best estimated delay possible (from the timing look up table) and the actual achieved delay.Timing deviation=|Delay sensitivity−Actual Delay achieved|
iii) wire-length deviation, is the deviation from the best estimated routed wire-length possible (from the net's placement bounding box) and the actual achieved routed wire-length (from the net's routing tree bounding box)Wire-length deviation=|HPWL (Placement)−HPWL (Routing tree)|
Further, in the course of routing design nets it is difficult to obtain feasible routing trees. This is because of potential routing resources locked by other nets or timing/wire-length constraints of nets exceeding the desired cut off region. Under such circumstances routers proceed to a rip-up and reroute phase. Normally, the entire design is ripped up and rerouted with no intelligence in identifying sets of nets whose rip-up and reroute will make the design feasible.